Bloom filter(まとめ)

1.前提

SPVはブロックヘッダと自分に関係のあるノードの情報しかもたない。

(全てのブロックやトランザクションについて検証することができない)

初期のSPVは全トランザクションをダウンロード後に自分に関係のないものを捨てていたので効率が悪かった。

→同期に時間がかる

これを解決するためにダウンロードする時点で、自分に関係のあるトランザクションのみを入手するようなフィルターをかけることにした。これがブルームフィルター(昔からある技術)

2.ブルームフィルタ

https://gyazo.com/681963a79d442f3b1b2ddf71b28a5453

図1:ブルームフィルタを用いたブロックの受信

filterload

リモートノードとのコネクションにブルームフィルタをセットする

filteradd

データ要素を現在のブルームフィルタにセットする

filterclear

ブルームフィルタを除去する

フィルタリングはScript PubKeyやScriptSigにプッシュする個別の要素に対して行われる

<詳細>

データの有無を効率的に判断するアルゴリズム。

ブルームフィルタはn個のビット列とk個のハッシュ関数で構成される

ex:10このビット列,２個のハッシュ関数の場合

最初はこんなかんじー

https://gyazo.com/a58dadb280971ea40c3d2c5d03ba119c

図:2ブルームフィルタの初期状態

次に、要素Aを追加してみる

結果的に、出力された数字のビットを１に変換する(この場合は3と9)

https://gyazo.com/ed0d2b4d1917c441cecfe5e8138f535d

図3:要素Aを追加したブルームフィルタ

同じように要素Bを追加する

https://gyazo.com/eacc6cc47babeef9bde5c19ba2507e12

図4:要素Bを追加したブルームフィルタ

このように、要素をハッシュにかけて出力された値をインデックスとしてビット列を走査し、そのビットの値全てが1であれば

要素が登録されている(可能性がある)と判断できる。

ん？？可能性がある？

そりゃそうだ。要素Aと同じ出力をもつ要素Cが存在する場合も考えられる

https://gyazo.com/b21864207ccb4452553c3fd81892f6da

この場合は実際に登録されていないにも関わらずデータが含まれている(可能性がある)と判定するため偽陽性の誤検出の可能性がある。(可能性、可能性くどいので詳しくはgbec動画で)

https://www.youtube.com/watch?v=T49UGXbDLME&list=PLr5Bi9qipPloWSpPrlSSjpiX-EDREtHFu&index=5

ちなみに、ハッシュを通してフィルタをかけている以上、一度追加したデータの削除はできない。

<フィルタに用いるマッチングアルゴリズム>

自分に関係のあるトランザクションを検出するマッチングアルゴリズム。

5ステップの途中で一つでもマッチすれば、以降のアルゴリズムは無視される。

1.トランザクションのハッシュを計算し、テストする。

2.トランザクションの各アウトプットについてScriptPubkeyの各要素(ScriptPubKey全体ではなく、ScriptPubKey内のハッシュや鍵などの要素)

3.トランザクションの各インプットについて、シリアライズされたOutPointをテストする

4.トランザクションの各インプットについて、そのScriptSig内の各要素(ScriptSig内には基本的にデータしかない)をテストする

5.上記のいずれにも合致しない場合はマッチしないと判断する